/*
 * =====================================================================================
 *
 *       Filename:  40biliion-rand-int.cpp
 *
 *    Description:  生成40亿个不重复的正整数数
 *
 *        Version:  1.0
 *        Created:  2011-11-11 13:40:55
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include <fstream>
#include <sstream>
#include <ctime>
#include <bitset>
#include <iostream>
#include <cstring>
#include <cstdlib>

unsigned int test_bit(char A[], unsigned int k)
{
    return (A[k >> 3] >> (k % 8)) & 0x01;
}

void set_bit(char A[], unsigned int k)
{
    A[k >> 3] |= 0x01 << (k % 8);
}

void clr_bit(char A[], unsigned int k)
{
    A[k >> 3] &= ~(0x01 << (k % 8));
}

int main(int argc, const char *argv[])
{
    const unsigned int maxcnt = 0x3FFFFFFF;
    const unsigned int cnt = 1000000000u;
    const unsigned int size = maxcnt >> 3;
    char *A = new char[size + 1];
    ::memset(A, 0, (size + 1)*sizeof(char));

    srand(unsigned(time(NULL)));
    std::stringstream ss;
    ss << "40biliion-rand-int.txt";
    std::ofstream file(ss.str().c_str());

    if (!file) {
        std::cout << "open file " << ss.str() << " failed." << std::endl;
        return 0;
    }

    unsigned int tmp = 0;

    clock_t start = clock();

    for (unsigned int i = 0; i < cnt; ++i) {
        do {
            tmp = rand() * rand() % maxcnt;
        } while (test_bit(A, tmp));

        set_bit(A, tmp);
        file << tmp << std::endl;
    }

    std::cout << "the running time is " << (clock() - start) / CLOCKS_PER_SEC << std::endl;

    delete [] A;

    return 0;
}


